package com.neu.struct.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 问题：如何创建B-树
 * 定义：一棵B-树是一棵具有以下性质的有根树（根为T.root）
 *     ①每个节点x有下面的属性
 *       a. x.n：当前存储在节点x中的关键字个数
 *       b. x.n个关键字本身以非降序存放，使得x.key(1)≤x.key(2)≤...≤x.key(x.n)。
 *       c. x.leaf：一个布尔值，如果x是叶节点，则为true；如果x为内部节点，则为false。
 *     ②每个内部节点x还包含x.n+1个指向其孩子的指针。叶节点没有孩子，所以它们的该属性没有定义。
 *     ③关键字x.key(i)对存储在各子树中的关键字范围加以分割：如果k(i)为任意一个存储在以x.c(i)为根
 *       的子树中的关键字，那么k(1)≤x.key()≤k(2)≤x.key(2)≤...≤x.key(x.n)≤k(x.n+1)
 *     ④每个叶子节点具有相同的深度，即树的高度h.
 *     ⑤每个节点所包含的关键字个数有上界和下界。用一个被称为B树的最小度数的固定正数t≥2来表示这些界限
 *       a.除了根节点以外的每个节点必须至少有t-1个关键字。因此，除了根节点以外的每个内部节点至少有t个孩子。
 *         如果树非空，根节点至少有一个关键字
 *       b.每个节点至多可包含2t-1个关键字。因此，一个内部节点至多可有2t个孩子。
 *         当一个节点恰好有2t-1个关键字时，称该节点是满的。
 *
 *     如果B树的一个内部节点x包含x.n个关键字，那么节点x就有x.n+1个孩子。节点x中的关键字就是分割点，
 *     它把节点x中所处理的关键字的属性分割为x.n+1个子域，每个子域都由x的一个孩子处理。当在一棵B树中查找
 *     一个关键字时，基于对存储在x中的x.n个关键字的比较，做出一个(x.n+1)路的选择
 *定理：如果n≥1，那么对任意一棵包含n个关键字、高度为h、最小度数t≥2的B树T又：
 *                      高度 h≤log(n+1)/2 (以t为底)
 *性质：①在B树中，每个节点中关键字从小到大排列，并且当该节点的孩子是非叶子节点时，该k-1个关键字
 *      正好是k个孩子包含的关键字的值域的划分。因为叶子节点不包含关键字，所以可以把叶子节点看成
 *      在树里并不存在的外部节点，指向这些外部节点的指针为空，叶子节点的数目正好等于树中所包含的关键字总数加1
 *     ②B树的高度仅随它所包含的节点数按对数增长
 *     ③B树上大部分的操作所需的磁盘存取次数与B树的高度是成正比的。
 *     ④叶子节点的数目等于关键字总数加1。
 * Created by lihongyan on 2015/11/16.
 */
public class BTree<E> {

    private class BTreeNode<E> implements Comparable<BTreeNode<E>>{

        private int number = 0;
        private List<E> keys = new ArrayList<E>();
        private List<BTreeNode<E>> children = new ArrayList<BTreeNode<E>>();
        private boolean isLeaf = false;
        public int getNumber() {
            return number;
        }
        public void setNumber(int number) {
            this.number = number;
        }
        public List<E> getKeys() {
            return keys;
        }
        public void setKeys(List<E> keys) {
            this.keys = keys;
        }
        public List<BTreeNode<E>> getChildren() {
            return children;
        }
        public void setChildren(List<BTreeNode<E>> children) {
            this.children = children;
        }
        public boolean isLeaf() {
            return isLeaf;
        }
        public void setIsLeaf(boolean isLeaf) {
            this.isLeaf = isLeaf;
        }
        @Override
        public int compareTo(BTreeNode<E> other) {

            return 0;
        }
    }
    /*
    * 约定
    * ①B树的根节点始终在主存中，这样无需对根节点做磁盘读取操作；
    *   当根节点被修改后，需要对根节点做一次磁盘写操作
    * ②任何被当做参数的节点在被传递之前，都要对他们先做一次磁盘写操作
    * */


    /*
    * 搜索B树：
    * 原理：搜索一棵B树和搜索一棵二叉搜索树相似，只是在每个节点所做的不是二叉或者“两路”分支选择，
    *      而是根据节点的孩子数做多路分支选择。
    *      更严格地说，对每个内部节点x，做的是一个(x.n+1)路的分支选择
    * 过程：B-Tree-Search()是定义在二叉搜索树上的Tree-Search()过程的一个直接推广。
    *      它的输入是一个指向某子树根节点x的指针，以及要在该子树中搜索的一个关键字k。
    *      因此，顶层调用的形式为：B-Tree-Search(T.root,k)。如果k在B树中，
    *      那么B-Tree-Search()返回的是由节点y和使得y.key(i)=k的下标i组成的有序对(y,i)；
    *      否则，过程返回null。
    * */
    public void b_tree_Search(BTreeNode<E> localRoot,E key){

    }
    /*
    * 创建B树：
    * 为创建一棵B树，先用B-Tree-Create()来创建一个空的根节点，然后调用B-Tree-Insert()来添加新的关键字。
    * */
    public void b_tree_create(){

    }
    /*
    * 插入关键字：
    * B树中插入一个关键字要比二叉搜索树中插入一个关键字复杂得多。像二叉搜索树中一样，要查找插入新关键字的叶节点的位置。
    * 然而，在B树中，不能简单的创建一个新的叶节点，然后将其插入，因为这样得到的树将不再是合法的B树。
    * 相反，我们是将新的关键字插入一个已经存在的叶节点上。由于不能将关键字插入一个满的叶节点，
    * 故引入一个操作，将一个满的节点y(有2t-1个关键字)按其中间关键字y.key(t)分裂为两个各含t-1个关键字的节点，
    * 中间关键字被提升到y的父节点，以标识两棵新数的划分点。但是如果y的父节点也是满的，就必须在插入新的关键字之前将其分裂，
    * 最终满节点的分裂会沿着树向上传播。与一棵二叉搜索树一样，可以在从树根到叶子这个单程向下过程中将一个新的关键字插入B树中，
    * 为了做到这一点，我们并不是等到找出插入过程中实际分裂的满节点时才做分裂，
    * 相反，当沿着树往下查找新的关键字所属位置时，就分裂沿途遇到的每个满节点(包括叶节点本身)。
    * 因此，每当要分裂一个节点y时，就能确保它的父节点不是满的了。
    * */
    public void b_tree_insert(){

    }
    /*
    * 分裂树中的节点
    * 过程：b_tree_split_child()的输入是一个非满的内部节点x(假定在主存中)
    * 和一个使x.c(i)(假定也在主存中)为x的满子节点的下标i。该过程把这个子节点分裂成两个，
    * 并调整x，使之包含多出来的孩子。要分裂一个满的根节点，首先要让根节点成为一个新的空根节点的孩子，
    * 这样才能使用b_tree_split_child()。树的高度因此增加1，分裂是树长高的唯一途径。
    * */
    public void b_tree_split_child(){

    }
    /*
    * 删除关键字：
    * 原理：B树上的删除操作与插入操作类似，只是略微复杂一点，因为可以从任意一个节点中删除一个关键字，
    *      而不仅仅是叶节点，而插入操作仅仅发生在叶节点上。而且当从一个内部节点删除一个关键字时，
    *      还要重新安排这个节点的孩子。与插入操作一样，必须控制因为删除操作而导致树的结构违反B树的性质，
    *      就与必须保证一个节点不会因为插入儿变得太大一样，必须保证一个节点不会在删除期间变得太小，
    *      (根节点除外，因为它允许有比最少关键字数t-1还少的关键字数)。
    *      在一个简单插入算法中，如果插入关键字的路径上节点满，可能需要向上回溯；与此类似，
    *      在一个简单删除算法中，当要删除关键字的路径上节点（非根节点）有最少关键字个数时，也可能需要向上回溯。
    * 过程：
    * 1.如果关键字k在节点x中，并且x是叶节点，则从x中删除k。
    * 2.如果关键字k在节点x中，并且x是内部节点，则做以下操作：
    *   a.如果在节点x中前于k的子节点y至少包含t个关键字，则找出k在以y为根的子树中的前驱k'，递归地删除k'，
    *     并在x中用k'代替k。（找到k'并删除它可在沿树下降的单过程中完成）
    *   b.如果在节点x中前于k的子节点y有少于t个关键字，则检查节点x中后于k的子节点z。如果z至少有t个关键字，
    *     则找出k在以z为根的子树中的后继k'。递归地删除k'，并在x中用k'代替k。
    *    （找到k'并删除它可在沿树下降的单过程中完成）
    *   c.否则，如果y和z都只含有t-1个关键字，则将k和z的全部合并进y，这样x就失去了k和指向z的指针，
    *     并且y现在只包含2t-1个关键字。然后释放z并递归地从y中删除k。
    * 3.如果关键字k当前不在内部节点x中，则确定必包含k的子树的根x.c(i)（如果k确实在树中）。
    *   如果x.c(i)只有t-1个关键字，必须执行步骤3a或3b来保证降至一个至少包含t个关键字的节点，
    *   然后，通过对x的某个合适的子节点进行递归而结束
    *   a.如果x.c(i)中只含有t-1个关键字，但是它的一个相邻的兄弟至少包含t个关键字，
    *     则将x中的某一个关键字将至x.c(i)中，将x.c(i)的相邻左兄弟或又兄弟的几个关键字升至x，
    *     将该兄弟中形影的孩子指针移到x.c(i)中，这样就是的x.c(i)增加了一个额外的关键字。
    *   b.如果x.c(i)以及x.c(i)的相邻兄弟都只包含t-1个关键字，则将x.c(i)与一个兄弟合并，
    *     即将x的一个关键字移至新合并的节点，使之称为该节点的中间关键字。
    * 由于一棵B树中的大部分关键字都存在叶节点中，所以在实际中，删除操作最经常用于从叶节点中删除关键字。
    * 这样b-tree-delete()过程只要沿树下降一趟即可，不需要向上回溯。然而，当要删除某个内部节点的关键字时，
    * 该过程也要沿树下降一趟，但可能还要返回删除了关键字的那个节点，以用其前驱或后继来取代被删除的关键字。
    * */
    public void b_tree_delete(){

    }
    public static void main(String[] args){

    }
}
